# -*- coding: utf-8 -*-
"""
硬币找零问题:假设有几种不同币值的硬币v1,v2,...,vn(单位元)。如果我们要支付w元，求至少需要多少个硬币。
"""
from typing import List


def coins_dp(values: List[int], target: int) -> int:
    """使用动态规划算法
    :param values: 可使用的硬币币值
    :param target: 支付的金额
    :return: 最少需要的硬币数量
    """
    # memo[i] 表示target为i时候，所需的最少硬币数。
    memo = [0] * (target + 1)
    # 0元的时候为0个
    memo[0] = 0

    # 最小的硬币面值
    values.sort()
    min_value = values[0]

    for i in range(1, target + 1):
        min_num = target // min_value + 1
        # 对于values中的所有n
        # memo[i] 为min(memo[i-n1],memo[i-n2],...) + 1
        for n in values:
            if i >= n:
                min_num = min(min_num, memo[i - n] + 1)
            else:  # values中的值需要从小到大排序
                break
        memo[i] = min_num
    print(memo)
    return memo[-1]


def coins_backtracking(values: List[int], target: int):
    """使用回溯算法
    :param values: 可使用的硬币币值
    :param target: 支付的金额
    :return: 最少需要的硬币数量
    """

    values.sort()
    min_value = values[0]
    min_num = target // min_value + 1

    def _coins_backtracking(curr_value: int, coins_count: int):
        nonlocal min_num
        nonlocal values
        nonlocal target

        if curr_value == target:
            min_num = min(min_num, coins_count)

        else:
            for n in values:
                if n + curr_value <= target:
                    _coins_backtracking(n + curr_value, coins_count + 1)

    _coins_backtracking(0, 0)

    return min_num


if __name__ == "__main__":
    values = [1, 3, 5]
    target = 23
    print(coins_dp(values, target))
    print(coins_backtracking(values, target))
